package Class031_位;

public class BitsetDesign {

}

class Bitset {
    public int[] bitset;
    private int size;
    private int ones;
    private int zeroes;
    //reverse is used to represent a flip operation.
    //eg, at one time the bit representation is
    //0101101011
    //if a flip is called
    //you do not necessarily need to flip all bit
    //just let reverse = !reverse
    //and change the num of ones and zeroes
    //originally, reverse = false, so 0 stands for 'not in bitmap', 1 = 'already in bitmap'
    //once flipped, 0 = 'already in bitmap', and 1 = 'not in bitmap'
    private boolean reverse;


    // Initializes the Bitset with size bits, all of which are 0.
    public Bitset(int size) {
        this.size = size;
        bitset = new int[(size + 31) / 32];
        ones = 0;
        zeroes = size;
        reverse = false;
    }

    //Updates the value of the bit at the index idx to 1.
    //If the value was already 1, no change occurs.
    public void fix(int idx) {
        int index = idx / 32;
        int bit = idx % 32;
        if(!reverse) {
            //if not reversed,
            //0 => not exist
            //1 => existed
            //if the bit at idx is 0, then it does not exist in bitmap yet.
            if((bitset[index] & (1 << bit)) == 0) {
                ones++;
                zeroes--;
                bitset[index] |= 1 << bit;
            }
        }else {
            //if reversed,
            //0 => existed
            //1 => not exist
            //if the bit at idx is 1, then it does not exist in bitmap yet.
            if((bitset[index] & (1 << bit)) != 0) {
                ones++;
                zeroes--;
                bitset[index] ^= 1 << bit;
            }
        }
    }

    //Updates the value of the bit at the index idx to 0.
    //If the value was already 0, no change occurs.
    public void unfix(int idx) {
        int index = idx / 32;
        int bit = idx % 32;
        if(!reverse) {
            if((bitset[index] & (1 << bit)) != 0) {
                ones--;
                zeroes++;
                bitset[index] ^= 1 << bit;
            }
        }else {
            if((bitset[index] & (1 << bit)) == 0) {
                ones--;
                zeroes++;
                bitset[index] |= 1 << bit;
            }
        }
    }

    //Flips the values of each bit in the Bitset.
    //In other words, all bits with value 0 will now have value 1 and vice versa.
    public void flip() {
        reverse = !reverse;
        int tmp = ones;
        ones = zeroes;
        zeroes = tmp;
    }

    //Checks if the value of each bit in the Bitset is 1.
    //Returns true if it satisfies the condition, false otherwise.
    public boolean all() {
        return zeroes == 0;
    }

    //Checks if there is at least one bit in the Bitset with value 1.
    //Returns true if it satisfies the condition, false otherwise.
    public boolean one() {
        return ones != 0;
    }

    //Returns the total number of bits in the Bitset which have value 1.
    public int count() {
        return ones;
    }

    //Returns the current composition of the Bitset.
    //Note that in the resultant string,
    //the character at the ith index should coincide with the value at the ith bit of the Bitset.
    public String toString() {
        StringBuilder str = new StringBuilder();
        int bits = 1;
        for(int i = 0; i < bitset.length; i++) {
            for(int j = 0; j < 32 && bits <= size; j++) {
                int cur = (bitset[i] >>> j) & 1;
                cur ^= reverse ? 1 : 0;
                str.append(cur);
                bits++;
            }
        }
        return str.toString();
    }
}
